package pseudoAssemblerCompiler.twopassassembler;

/**
 * Реализация бинарного дерева поиска
 *
 * User: Роман
 * Date: 29.05.12
 * Time: 10:25
 */
public class BinarySearchTree<T> {

    /**
     * Корень дерева
     */
    private Node root;

    /**
     * Поиск объекта по ключу
     * @param key
     * @return узел дерева с помещенным в него объектом
     */
    public Node find(int key) {
        Node current = root; // start at root

        //Пока не нашли искомый узел
        while (current.getKey() != key)
        {
            // Если ключ меньше, чем ключ текущего элемента,
            // то идём налево, иначе направо
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            // если текущий узел равен null(нет потомков),
            // значит узел с таким ключём не найден
            if (current == null)
                return null;
        }
        return current; // узел найден
    }

    /**
     * Добавление объекта в дерево
     * @param id
     * @param object
     */
    public void insert(int id, T object) {
        //Создаём новый узел
        Node newNode = new Node();
        newNode.setKey(id);
        newNode.setData(object);

        // если корень не задан, то инициализируем корень
        if (root == null) {
            root = newNode;
        } else {
            Node current = root; // start at root
            Node parent;

            /*
            * Проходим по дереву пока не найдем узел без потомков,
            * если нашли, то добавляем новый узел
            */
            while (true)
            {
                parent = current;
                if (id < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) { // нет потомка - добавляем
                        parent.setLeftChild(newNode);
                        return; //выходим из цикла
                    }
                } else {
                    current = current.getRightChild();
                    if (current == null) { // нет потомка - добавляем
                        parent.setRightChild(newNode);
                        return; //выходим из цикла
                    }
                }
            }
        }
    }

    public Node minimum() // returns node with minimum key value
    {
        Node current, last = null;
        current = root; // start at root
        while (current != null) // until the bottom,
        {
            last = current; // remember node
            current = current.getLeftChild(); // go to left child
        }

        return last;
    }

    /**
     * Удаляем узел по ключу
     * @param key
     * @return true - если узел удалён
     */
    public boolean delete(int key)
    {
        //Предполагаем, что дерево не пустое
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;

        //Ищем узел по ключу
        while (current.getKey() != key) {
            parent = current;

            if (key < current.getKey()) { //идём в левое поддерево
                isLeftChild = true;
                current = current.getLeftChild();
            } else { // иначе в правое
                isLeftChild = false;
                current = current.getRightChild();
            }

            if (current == null) {// узел не найден
                return false; // и не был удалён
            }
        }

        // Найден узел для удаления, если нет потомков, то просто удаляем его
        if (current.getLeftChild() == null &&
                current.getRightChild() == null) {
            if (current == root) { // если это корень,
                root = null; // то дерево становиться пустым
            } else if (isLeftChild) {
                parent.setLeftChild(null); // удаляем левого потомка
            } else {
                parent.setRightChild(null); // удаляем правого потомка
            }
        } else if (current.getRightChild() == null) { // если нет правого потомка, то заменяем левым поддеревом
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild) // left child of parent
                parent.setLeftChild(current.getLeftChild());
            else // right child of parent
                parent.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) { // если нет левого потомка, то заменяем правым поддеревом
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild) // left child of parent
                parent.setLeftChild(current.getRightChild());
            else // right child of parent
                parent.setRightChild(current.getRightChild());
        } else { // два потомка, то заменяем симметричным приемником

            Node successor = getSuccessor(current); //Получаем приемника по удаляемому узлу

            // добавляем к родителю удаляемого узла, его приемника
            if (current == root) //если удаляемый узел - корень,
                root = successor; // то заменяем корень, приемником
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
            // connect successor to current’s left child
            successor.setLeftChild(current.getLeftChild());
        }
        // потомок не может иметь левого потомка
        return true;
    }

    // returns node with next-highest value after delNode
    // goes to right child, then right child’s left descendants
    /**
     * Возвращаем узел со следующим наибольшим значением после удаляемого узла,
     * который становится правым потомком,
     *
     * @param delNode
     * @return
     */
    private Node getSuccessor(Node delNode) {

        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.getRightChild(); // идём по правому потомку

        while (current != null) { // пока не останится левых потомков
            successorParent = successor;
            successor = current;
            current = current.getLeftChild(); // идём по левому потомку
        }

        // если приемник не является правым потомком удаляемого узла
        if (successor != delNode.getRightChild()) {
            successorParent.setLeftChild(successor.getRightChild());
            successor.setRightChild(delNode.getRightChild());
        }
        return successor;
    }

}
